import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Node{
    public char val;
    public Node left;
    public Node right;
    public Node(char val){
        this.val = val;
    }

}
public class BinaryTree {
    public Node createTree() {
        Node A = new Node('A');
        Node B = new Node('B');
        Node C = new Node('C');
        Node D = new Node('D');
        Node E = new Node('E');
        Node F = new Node('F');
        Node G = new Node('G');
        Node H = new Node('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    //非递归
     void preOrderTraversal3(Node root){
        Stack<Node> stack = new Stack<>();
        System.out.print("先序遍历：");
        if (root != null){
            stack.push(root);
            while(!stack.isEmpty()){
                root = stack.pop();
                System.out.print(root.val+" ");
                if (root.right != null){
                    stack.push(root.right);
                }
                if (root.left != null){
                    stack.push(root.left);
                }
            }
        }
    }
    //非递归
    void inOrderTraversal1(Node root){
        Stack<Node> stack = new Stack<>();
        System.out.print("中序遍历：");
            while (root != null || !stack.isEmpty()){
                while(root != null){
                    stack.push(root);    //一直放左
                    root = root.left;
                }
                if (!stack.isEmpty()){
                    root =  stack.pop();
                    System.out.print(root.val+" ");
                    root = root.right;
                }
            }
        }
    //非递归
    void postOrderTraversal1(Node root){
        Stack<Node> stack = new Stack<>();
        System.out.print("后序遍历:");
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.peek();
                if (root.right != null) {
                    stack.push(root.right);
                    root = root.right;
                } else {
                    root = stack.pop();
                    System.out.println(root.val + " ");
                    root = stack.peek();
                }

        }
    }
    //获取高度
    public int getHeight(Node root){
        if (root == null){
            return 0;
        }
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return Math.max(left,right)+1;
    }

    //递归前序遍历
    public void preOrderTraversal(Node root){
        if (root == null)return;
        System.out.print(root.val+" ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

    //递归中序遍历
    void inOrderTraversal(Node root){
        if (root == null)return;
        inOrderTraversal(root.left);
        System.out.print(root.val + " ");
        inOrderTraversal(root.right);
    }

    //递归后序遍历
    void postOrderTraversal(Node root){
        if (root == null)return;
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val+" ");
    }

    //求节点个数 遍历
    static int size = 0;
    void getSize1(Node root){
        if(root == null)return;
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }
    //求节点个数 子问题
    int getSize2(Node root) {
        if (root == null)return 0;
        return getSize2(root.left) + getSize2(root.right) + 1;
    }

    //求叶子节点个数 遍历
    static int leafSize = 0;
    void getLeafSize1(Node root){
        if(root == null)return;
        if (root.left == null && root.right == null){
            leafSize++;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }

    // 子问题思路-求叶子结点个数
    int getLeafSize2(Node root){
        if (root == null)return 0;
        if (root.left == null && root.right == null){
            return 1;
        }
        return getLeafSize2(root.left) + getLeafSize2(root.right);
    }

    // 子问题思路-求第 k 层结点个数
    int getKLevelSize(Node root,int k){
        if (root == null)return 0;
        if (k == 1){
            return 1;
        }
        return getKLevelSize(root.left,k-1) + getKLevelSize(root.right,k-1);
    }

    Node find(Node root, char val){
        if (root == null)return null;
        if (root.val == val)return root;
        Node r= find(root.left,val);
        if (r != null){
            return r;
        }
        r =  find(root.right,val);
        if (r != null){
            return r;
        }
        return null;
    }
    //判断是否为完全二叉树
    boolean isCompleteTree(Node root){
        if (root == null)return true;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        // 1.当cur！=null放入元素，当弹出的元素为null时结束循环
        while (!queue.isEmpty()){
            Node cur = queue.poll(); //弹出根
            if (cur != null){   //判断根不为空时 放入左右孩子
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        //2.判断队列中是否还有节点，如果有为false
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            if (cur != null){
                return false;
            }
        }
        return true;
    }

    //层序遍历
    void levelOrderTraversal(Node root){
        if(root == null)return;
        Queue<Node> queue =new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node cur = queue.poll();
            System.out.print(" "+cur.val);
            if (cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right != null){
                queue.offer(cur.right);
            }
        }
    }
}
